# 两整数之和： https://leetcode-cn.com/problems/sum-of-two-integers/

# 错误
class Solution:
    def getSum(self, a: int, b: int) -> int:
        """
            1. 在不考虑进位的条件下： 
            1 + 1 = 0 ; 1 + 0 = 1; 0 + 0 = 0 恰好符合 异或的原则（同出0，异出1）
            异或运算就相当于是 无进位的加法。 
            2. 如果计算进位：
            1 + 1 进位是 1；  1 + 0 和 0 + 0 进位是 0，恰好符合 按位&的原则， &完之后， 应该 << 左移1位，这是它需要进位的位置

            进位数值 加上 无进位加法计算的数值，就是最终结果（ 所以要保证最终的计算，不再产生进位，那么无进位加法的结果就是正确的！）
            # 在Python中是错误的。因为Python的左移会一直将一个数字放大，没有限制。 但是这个位运算的技巧，应当是有溢出的，例如32位整数，只去32位
            测试用例 1 -1， 在下面的代码中时出错的，一直循环~ 。我们需要限制位数。需要设置掩码！
        """
        # 第一次计算无进位加法
        he = a ^ b     
        # 对应的进位
        jinwei = (a & b) << 1
        he1 = he

        # 循环, 判断进位是否为0，如果为0， 那么 异或的 无进位结果就是对的，直接返回
        while jinwei != 0:
            # 否则 和 等于 和 加上 进位
            he1 = he ^ jinwei
            # 判断下 和加进位 是否还有 进位
            jinwei = (jinwei & he) << 1
            # 此时的he 要更新为 he1, 因为 如果这次的 进位还不是， 那么就需要这次 异或的结果(he1)加上jinwei.  问不上 he(上次的结果)加上进位
            he = he1
        
        return he1


# 下面是改进后的代码
class Solution(object):
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        # 2^32
        MASK = 0x100000000
        # 整型最大值
        MAX_INT = 0x7FFFFFFF
        MIN_INT = MAX_INT + 1
        while b != 0:
            # 计算进位
            carry = (a & b) << 1 
            # 取余范围限制在 [0, 2^32-1] 范围内
            a = (a ^ b) % MASK
            b = carry % MASK
        return a if a <= MAX_INT else ~((a % MIN_INT) ^ MAX_INT)   



s = Solution()
rst = s.getSum(-1, -99)
print(rst)



# 1001 --> 1111

# 1111  ^
# 0001
# -------
# 1110    -2

# & 
# 0001 >>1   0010


# 1110 ^
# 0010
# -----
# 1100     -4 

# & 0010 >> 1   0100   4 

# 1100  ^  
# 0100        
# -----
# 1000     1111  --> 1000

# & 1000


# 1000 ^ 
# 1000

# 0000   

# 10000
# 00000
# -----
# 10000 

# 11111
# 10000
# -----





# 1101 
# 1010 --> -2
 
